class Solution1 {
    public static void main(String[] args) {
        String arr = "abc" ;
        System.out.println(countSubstrings(arr));
    }
    public static int countSubstrings(String s) {
         char[] arr = s.toCharArray() ;
         int len = s.length() ;
         boolean[][] dp = new boolean[len][len] ; 
          int sum = 0 ;
         for(int i=len-1 ; i >= 0 ; i --){
             for(int j=i ; j < len ; j ++){
                 if(arr[i] == arr[j])
                dp[i][j] = i+1<j? dp[i+1][j-1]:true ;
               if(dp[i][j]){
                sum += 1 ;
               }
             }
         }
        return sum ;
    }
}